package geekstudy.week5;

/**
 *
 * https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/
 * 1011. 在 D 天内送达包裹的能力
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：9 ms, 在所有 Java 提交中击败了96.90% 的用户
 * 内存消耗：41.5 MB, 在所有 Java 提交中击败了62.19%
 *
 */
public class Week5CapacityToShipPackagesWithinDDays {

    public int shipWithinDays(int[] weights, int days) {
        int weightSum = 0;
        int maxWeight = 0;
        for(int weight : weights) {
            weightSum += weight;
            maxWeight = Math.max(maxWeight, weight);
        }

        int left = Math.max(maxWeight, weightSum / days);
        int right = maxWeight * (weights.length / days + 1);

        while(left <= right) {
            int mid = (left + right) / 2;
            if(canLoad(weights, days, mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    public boolean canLoad(int[] weights, int days, int load) {
        int tmp = load;
        for(int weight : weights) {
            if(weight <= load) {
                load -= weight;
            } else {
                days--;
                load = tmp - weight;
            }
            if(days <= 0) {
                return false;
            }
        }
        return true;
    }
}
